package cn.cxq.learning.sort;

import java.util.Arrays;

/**
 * 归并排序：使用到了分治的思想（先把任务分下去，然后从简单到复杂，从细小到具体执行程序代码）
 */
public class MergeSort {

    public static int[] printSort(int[] arr, int left, int right, int[] temp){

        int middle = (left + right) / 2;
        if (left < right) {
            printSort(arr, left, middle, temp);
            printSort(arr, middle + 1, right, temp);
            printMerge(arr, left, middle, right, temp);
        }
        return arr;
    }

    private static void printMerge(int[] arr, int left, int middle, int right, int[] temp) {

        int index = 0;
        int i = left;
        int j = middle + 1;

        while (i <= middle && j <= right)
            if (arr[i] <= arr[j]) temp[index ++] = arr[i ++];
            else temp[index ++] = arr[j ++];

        while (i <= middle) temp[index ++] = arr[i ++];
        while (j <= right) temp[index ++] = arr[j ++];

        index = 0;
        int tempLeft = left;

        while (tempLeft <= right) arr[tempLeft ++] = temp[index ++];

        System.out.println(Arrays.toString(arr));
    }

    public static int[] sort(int[] arr, int left, int right, int[] temp){

        int middle = (left + right) / 2;
        if (left < right) {
            sort(arr, left, middle, temp);
            sort(arr, middle + 1, right, temp);
            merge(arr, left, middle, right, temp);
        }
        return arr;
    }

    private static void merge(int[] arr, int left, int middle, int right, int[] temp) {

        int index = 0;
        int i = left;
        int j = middle + 1;

        while (i <= middle && j <= right)
            if (arr[i] <= arr[j]) temp[index ++] = arr[i ++];
            else temp[index ++] = arr[j ++];

        while (i <= middle) temp[index ++] = arr[i ++];
        while (j <= right) temp[index ++] = arr[j ++];

        for (int k = left; k < index; k++) {
            arr[left] = temp[left];
        }
    }
}
